/*
题目: 视频拼接
你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。

使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。

甚至可以对这些片段自由地再剪辑：

    例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

https://leetcode.cn/problems/video-stitching/
 */
public class VideoStitching {
    public int videoStitching(int[][] clips, int time) {
        int n = clips.length;
        // 拼接以完成 [0, i] 时间段的视频 需要的最少片段数量
        int[] dp = new int[time + 1];
        Arrays.fill(dp, 250);
        dp[0] = 0;

        // 完成 [0, i] 时间段的视频
        for (int i = 1; i <= time; i ++) {
            for (int[] clip : clips) {
                // 开始时间肯定要小于 i, 结束时间要大于等于 i
                if (clip[0] <= i && clip[1] >= i) {
                    dp[i] = Math.min(dp[i], dp[clip[0]] + 1);
                }
            }
        }

        return dp[time] == 250 ? -1 : dp[time];
    }
}
